package LeetCode;

import java.awt.desktop.PreferencesEvent;
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class LeetCodeMain5 {
    public int search(int[] nums, int target) {
        if (nums.length==1){
            if (nums[0]==target){
                return 0;
            }return -1;
        }
        if (nums==null||nums.length==0){
            return -1;
        }
        int n= nums.length;
        int left=0;
        int right=n-1;
        while (left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        }
        return -1;
    }
    public int maxArea(int[] height) {
        int max=0;
        int left=0;
        int right=height.length-1;
        while (left<right){
            max=Math.max(max,Math.min(height[left],height[right])*(right-left));
            if (height[left]<height[right]){
                left++;
            }
            else {
                right--;
            }
        }
        return max;
    }
//    StringBuilder st1=new StringBuilder();
//    StringBuilder st2=new StringBuilder();
//    public String longestPalindrome(String s) {
//        backstrack(s,0);
//        return st2.toString();
//    }
//    public void backstrack(String s,int startIndex){
//        if (st1.length()>st2.length()){
//            st2=st1;
//            return;
//        }
//        for (int i=startIndex;i<s.length();i++){
//            if (isDigita(s,startIndex,i)){
//                st1.append(s.substring(startIndex,i+1));
//            }else {
//                continue;
//            }
//            backstrack(s,i+1);
//            st1.deleteCharAt(st1.length()-1);
//        }
//    }
//    public boolean isDigita(String s,int start,int end){
//        char[] ch=s.toCharArray();
//        for (int i = start,j = end; i < j; i++, j--) {
//            if (ch[i] != ch[j]) {
//                return false;
//            }
//        }
//        return true;
//    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1==null){
            return l2;
        }if (l2==null){
            return l1;
        }
        ListNode n1=new ListNode(-1);
        ListNode n2=n1;
        int tmp=0;
        while (l1!=null||l2!=null){
            if (l1!=null){
                tmp+=l1.val;
                l1=l1.next;
            }
            if (l2!=null){
                tmp+=l2.val;
                l2=l2.next;
            }
            ListNode n3=new ListNode(tmp%10);
            tmp=tmp/10;
            n2.next=n3;
            n2=n2.next;
        }
        if (tmp!=0){
            ListNode n3=new ListNode(tmp);
            n2.next=n3;
            n2=n2.next;
        }
        return n1.next;
    }
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int[] arr=new int[2];
        for (int i = 0; i < nums.length; i++) {
            int sum=target-nums[i];
            if (map.containsKey(sum)){
                arr[0]=i;
                arr[1]=map.get(sum);
            }map.put(nums[i],i);
        }
        return arr;
    }
        public int[] twoSum1(int[] nums, int target) {
        int[] arr=new int[2];
        int k=1;
        for (int i = 0; i < nums.length-1; i++) {
            int j=i+1;
            for (;j<nums.length;j++){
                if (target==(nums[i]+nums[j])){
                    arr[0]=i;
                    arr[1]=j;
                    k=0;
                    break;
                }
                if (k==0){
                    break;
                }
            }
        }
        return arr;
    }
}
